using System;
using System.Collections.Generic;
using System.Text;
using System.Data;

namespace Blimpbots.Recognition.Algorithms
{
    /// <summary>
    /// This class implement a KMeans clustering algorithm
    /// </summary>
    public class KMeans
    {
        public KMeans()
        {
        }

        /// <summary>
        /// Calculates the Euclidean Distance Measure between two data points
        /// </summary>
        /// <param name="X">An array with the values of an object or datapoint</param>
        /// <param name="Y">An array with the values of an object or datapoint</param>
        /// <returns>Returns the Euclidean Distance Measure Between Points X and Points Y</returns>
        public double EuclideanDistance(double[] X, double[] Y, double[] dimWeight)
        {
            int count = 0;
            double distance = 0.0;
            double sum = 0.0;

            if (X.GetUpperBound(0) != Y.GetUpperBound(0))
                throw new System.ArgumentException("the number of elements in X must match the number of elements in Y");
            else
                count = X.Length;

            for (int i = 0; i < count; i++)
                sum = sum + Math.Pow( dimWeight[i] * (X[i] - Y[i]), 2);

            distance = Math.Sqrt(sum);
            return distance;
        }


        /// <summary>
        /// Calculates the Manhattan Distance Measure between two data points
        /// </summary>
        /// <param name="X">An array with the values of an object or datapoint</param>
        /// <param name="Y">An array with the values of an object or datapoint</param>
        /// <returns>Returns the Manhattan Distance Measure Between Points X and Points Y</returns>
        public double ManhattanDistance(double[] X, double[] Y)
        {
            int count = 0;
            double distance = 0.0;
            double sum = 0.0;

            if (X.GetUpperBound(0) != Y.GetUpperBound(0))
                throw new System.ArgumentException("the number of elements in X must match the number of elements in Y");
            else
                count = X.Length;

            for (int i = 0; i < count; i++)
                sum = sum + Math.Abs(X[i] - Y[i]);

            distance = sum;
            return distance;
        }

        /// <summary>
        /// Calculates The Mean Of A Cluster OR The Cluster Center
        /// </summary>
        /// <param name="cluster">
        /// A two-dimensional array containing a dataset of numeric values
        /// </param>
        /// <returns>
        /// Returns an Array Defining A Data Point Representing The Cluster Mean or Centroid
        /// </returns>
        public double[] ClusterMean(double[][] cluster)
        {
            double[] dataSum;
            double[] centroid;

            int rowCount = cluster.Length;
            int fieldCount = cluster[0].Length;

            dataSum = new double[fieldCount];
            centroid = new double[fieldCount];

            //((20+30)/2), ((170+160)/2), ((80+120)/2)
            for (int j = 0; j < fieldCount; j++)
            {
                for (int i = 0; i < rowCount; i++)
                    dataSum[j] = dataSum[j] + cluster[i][j];

                centroid[j] = (dataSum[j] / rowCount);
            }

            return centroid;
        }


        public ClusterCollection ClusterDataSet(int clusterCount, double[][] data, double[] dimWeight, int maxRepetitions)
        {
            ClusterCollection bestCollection = null;
            double bestSquaredError = double.MaxValue;
            double percentThresh = 0.005; // When a better clustering is found,
                                          // terminate if it doesn't improve the best
                                          // by more than this percent.

            // TODO: Verify this works for this corner case
            if (data.Length == 0) return new ClusterCollection();

            for (int i = 0; i < maxRepetitions; i++)
            {
                ClusterCollection cc = ClusterDataSet(clusterCount, data, dimWeight);
                double sqE = cc.TotalSquaredError();

                if (sqE <= bestSquaredError)
                {
                    double percentBetter = (bestSquaredError - sqE) / bestSquaredError;
                    bestSquaredError = sqE;
                    bestCollection = cc;
                    if (percentBetter < percentThresh) break;
                }
            }

            return bestCollection;
        }

        /// <summary>
        /// Separates a dataset into clusters or groups with similar characteristics
        /// </summary>
        /// <param name="clusterCount">The number of clusters or groups to form</param>
        /// <param name="data">An array containing data that will be clustered</param>
        /// <returns>A collection of clusters of data</returns>
        public ClusterCollection ClusterDataSet(int clusterCount, double[][] data, double[] dimWeight)
        {
            int rowCount = data.Length;
            int stableClustersCount = 0;

            Cluster cluster = null;
            ClusterCollection clusters = new ClusterCollection();

            #region Generate random cluster seed
            Random r = new Random();
            int[] indices = new int[clusterCount];
            for(int i = 0; i < clusterCount; i++)
            {
                indices[i] = r.Next(data.Length);
                for(int j = 0; j < i; j++)
                    if(indices[i] == indices[j])
                    {
                        i--; break; // Backtrack.  Dupe detected.
                    }
            }
            #endregion

            //setup seed clusters
            for (int i = 0; i < clusterCount; i++)
            {
                cluster = new Cluster();
                cluster.Add(data[indices[i]], i);
                clusters.Add(cluster);
            }

            //do actual clustering
            int iterationCount = 0;
            while (stableClustersCount != clusters.Count)
            {
                iterationCount++;
                stableClustersCount = 0;

                //Do actual clustering
                ClusterCollection newClusters = this.ClusterDataSet(clusters, data, dimWeight);

                for (int clusterIndex = newClusters.Count-1; clusterIndex >= 0; clusterIndex--)
                {
                    double[] originalClusterMean = clusters[clusterIndex].ClusterMean;
                    // TODO: This is a rare case and hasn't been tested much
                    if (newClusters[clusterIndex].Count == 0)
                        newClusters.RemoveAt(clusterIndex);
                    else
                    {
                        double[] newClusterMean = newClusters[clusterIndex].ClusterMean;
                        double distance = this.EuclideanDistance(newClusterMean, originalClusterMean, dimWeight);
                        if (distance == 0)
                        {
                            stableClustersCount++;
                        }
                    }
                }
                clusters = newClusters;
            }

            return clusters;
        }


        /// <summary>
        /// Seperates a dataset into clusters or groups with similar characteristics
        /// </summary>
        /// <param name="clusters">A collection of data clusters</param>
        /// <param name="data">An array containing data to b eclustered</param>
        /// <returns>A collection of clusters of data</returns>
        public ClusterCollection ClusterDataSet(ClusterCollection clusters, double[][] data, double[] dimWeight)
        {
            double[] clusterMean;
            double firstClusterDistance = 0.0;
            double secondClusterDistance = 0.0;
            int rowCount = data.Length;
            int position = 0;

            // create a new collection of clusters
            ClusterCollection newClusters = new ClusterCollection();
            for (int count = 0; count < clusters.Count; count++)
            {
                Cluster newCluster = new Cluster();
                newClusters.Add(newCluster);
            }

            if (clusters.Count <= 0)
            {
                throw new SystemException("Cluster Count Cannot Be Zero!");
            }

            for (int row = 0; row < rowCount; row++)
            {
                for (int cluster = 0; cluster < clusters.Count; cluster++)
                {
                    clusterMean = clusters[cluster].ClusterMean;

                    if (cluster == 0)
                    {
                        firstClusterDistance = this.EuclideanDistance(data[row], clusterMean, dimWeight);
                        position = cluster;
                    }
                    else
                    {
                        secondClusterDistance = this.EuclideanDistance(data[row], clusterMean, dimWeight);

                        if (firstClusterDistance > secondClusterDistance)
                        {
                            firstClusterDistance = secondClusterDistance;
                            position = cluster;
                        }
                    }
                }

                newClusters[position].Add(data[row], row);
            }

            return newClusters;
        }

    }



    /// <summary>
    /// A class containing a group of data with similar characteristics (cluster)
    /// </summary>
    public class Cluster : System.Collections.CollectionBase
    {
        private struct ClusterItem
        {
            public double[] value;
            public int index;
            public ClusterItem(double[] value, int index) 
            {
                this.value = value;
                this.index = index;
            }
        }

        private List<KeypointMatch> _matches;
        public List<KeypointMatch> Matches
        {
            get { return _matches; }
            set { _matches = value; }
        }

        private double[] _clusterSum;
        /// <summary>
        /// The sum of all the data in the cluster
        /// </summary>
        public double[] ClusterSum
        {
            get { return this._clusterSum; }
        }

        public double Median(int dim)
        {
            if(List.Count == 0) return 0; // Degenerate case

            double[] values = new double[List.Count];
            for (int i = 0; i <  List.Count; i++)
                values[i] = this[i][dim];
            Array.Sort(values);

            if (values.Length % 2 == 1) // odd ... just grab the middle
                return values[values.Length / 2];
            else // even ... so average the middle two
                return (values[values.Length / 2] 
                     + values[(values.Length / 2) + 1]) / 2.0;
        }

        public CentroidEstimate Centroid {
            get
            {
                double[] clusterMean = ClusterMean;

                CentroidEstimate ce;
                ce.X = clusterMean[0];
                ce.Y = clusterMean[1];
                ce.Scale = clusterMean[2];

                return ce;
            }
        }

        private double[] _clusterMean;
        /// <summary>
        /// The mean of all the data in the cluster
        /// </summary>
        public double[] ClusterMean
        {
            get
            {
                for (int count = 0; count < this[0].Length; count++)
                {
                    this._clusterMean[count] = (this._clusterSum[count] / this.List.Count);
                }
                return this._clusterMean;
            }
        }

        public double TotalSquaredError()
        {
            double[] clusterMean = ClusterMean;
            double sumSqErr = 0;

            for (int d = 0; d < this[0].Length; d++)
            {
                for (int i = 0; i < this.List.Count; i++)
                    sumSqErr += Math.Pow(this[i][d] - clusterMean[d], 2);
            }

            return sumSqErr;
        }

        public double ComputeStandardDeviation(int[] dims)
        {
            double[] clusterMean = ClusterMean;
            double sumSqErr = 0;

            // Variance of 1 item is defined 0
            if(this.List.Count == 1) return 0;

            for (int d_i = 0; d_i < dims.Length; d_i++)
            {
                int d = dims[d_i];
                for (int i = 0; i < this.List.Count; i++)
                    sumSqErr += Math.Pow(this[i][d] - clusterMean[d], 2);
            }

            double var = sumSqErr / (this.List.Count - 1);
            return Math.Sqrt(var);
        }

        /// <summary>
        /// Adds a single dimension array data to the cluster
        /// </summary>
        /// <param name="data">A 1-dimensional array containing data that will be added to the cluster</param>
        public virtual void Add(double[] data, int idx)
        {
            this.List.Add(new ClusterItem(data,idx));

            if (this.List.Count == 1)
            {
                this._clusterSum = new double[data.Length];
                this._clusterMean = new double[data.Length];
            }

            for (int count = 0; count < data.Length; count++)
            {
                this._clusterSum[count] = this._clusterSum[count] + data[count];
            }
        }

        public int OriginalIndex(int Index)
        {
            return ((ClusterItem)this.List[Index]).index;
        }

        /// <summary>
        /// Returns the one dimensional array data located at the index
        /// </summary>
        public virtual double[] this[int Index]
        {
            get
            {
                return ((ClusterItem)this.List[Index]).value;
            }
        }
    }

    /// <summary>
    /// A collection of Cluster objects or Clusters
    /// </summary>
    public class ClusterCollection : System.Collections.CollectionBase
    {
        /// <summary>
        /// Adds a Cluster to the collection of Clusters
        /// </summary>
        /// <param name="cluster">A Cluster to be added to the collection of clusters</param>
        public virtual void Add(Cluster cluster)
        {
            this.List.Add(cluster);
        }

        public double TotalSquaredError()
        {
            double sumSqError = 0;
            foreach (object oC in List)
                sumSqError += ((Cluster)oC).TotalSquaredError();
            return sumSqError;
        }

        /// <summary>
        /// Returns the Cluster at this index
        /// </summary>
        public virtual Cluster this[int Index]
        {
            get
            {
                //return the Neuron at IList[Index] 
                return (Cluster)this.List[Index];
            }
        }
    }

}
